package zuochengyun.chapter5;

//添加最少字符串使整体都是回文字符串
public class MinCharToPalidrome {

	public static void main(String[] args) {
		String str = "A1BC22DE1F";
		String lps = "1221";
		MinCharToPalidrome object = new MinCharToPalidrome();
		object.getPalidrome2(str, lps);
	}
	
	public int[][] getDP(char[] str){
		//dp[i][j]表示str[i...j]最少添加几个字符可以使str[i...j]整体都是回文串
		int[][] dp = new int[str.length][str.length];
		//只有一个字符时dp[i][j] = 0; 显然dp[0][0] = 0;
		//如果有两个字符时，如果两个字符相等，那么就等于0，如果两个不相等，就等于1
		
		//dp[i][j - 1]表示str[i...j-1]变成回文串，然后再在左边加入str[j]
		//如果大于两个时，dp[i][j] = min{dp[i][j - 1], dp[i + 1][j]} + 1	(str[i] != str[j])
		//				dp[i][j] = dp[i + 1][j - 1];	(str[i] == str[j])
		for (int j = 1; j < dp.length; j++) {
			dp[j - 1][j] = str[j - 1] == str[j] ? 0 : 1;
			for (int i = j - 2; i >= 0; i--) {
				if(str[i] == str[j]){
					dp[i][j] = dp[i + 1][j - 1];
				}else{
					dp[i][j] = Math.min(dp[i][j - 1], dp[i + 1][j]) + 1;
				}
			}
		}
		return dp;
	}
	
	public String getPalidrome(String str){
		if(str == null || str.length() < 2){
			return str;
		}
		char[] chas = str.toCharArray();
		int[][] dp = getDP(chas);
		//添加字符串之后的长度
		char[] res = new char[chas.length + dp[0][chas.length - 1]];
		int i = 0;
		int j = chas.length - 1;
		int resLeft = 0;
		int resRight = res.length - 1;
		while(i <= j){
			if(chas[i] == chas[j]){
				res[resLeft++] = chas[i++];
				res[resRight--] = chas[j--];
			}else if(dp[i][j - 1] < dp[i + 1][j]){
				//此时说明是先扩展str[j]
				res[resLeft++] = chas[j];
				res[resRight--] = chas[j--];
			}else{
				//此时说明是先扩展str[i]
				res[resLeft++] = chas[i];
				res[resRight--] = chas[i++];
			}
		}
		return String.valueOf(res);
	}
	
	
	//如果已知最长回文子序列字符串strlps
	//那么可以采取“剥洋葱”的方式来将时间复杂度调整到O(N)
	public String getPalidrome2(String str, String strlps){
		if(str == null || str.equals("")){
			return "";
		}
		//比如A1BC22DE1F, lps为1221
		//首先找到最外层的1 1，然后将str中1   1 的外层的左边和右边变成回文
		//左边的1左边的记为leftPart(此时为A)，右边的1右边的即为rightPart(此时为B)
		//然后leftPart + (rightPart的逆序)   rightPart + (leftPart的逆序)
		char[] chas = str.toCharArray();
		char[] lps = strlps.toCharArray();
		char[] res = new char[chas.length * 2 - lps.length];
		int chasLeft = 0;
		int chasRight = chas.length - 1;
		int lpsLeft = 0;
		int lpsRight = lps.length - 1;
		int resLeft = 0;
		int resRight = res.length - 1;
		int tempLeft = 0;
		int tempRight = 0;
		while(lpsLeft <= lpsRight){
			tempLeft = chasLeft;
			tempRight = chasRight;
			//找到chars中与lps相等的那个字符
			while(chas[chasLeft] != lps[lpsLeft]){
				chasLeft++;
			}
			while(chas[chasRight] != lps[lpsRight]){
				chasRight--;
			}
			set(res, resLeft, resRight, chas, chasLeft, chasRight,tempLeft, tempRight);
			//此时调整resLeft和resRight
			resLeft += chasLeft - tempLeft + tempRight - chasRight;
			resRight -= chasLeft - tempLeft + tempRight - chasRight;
			//将lps的每一层加入到res中
			res[resLeft++] = chas[chasLeft++];
			res[resRight--] = chas[chasRight--];
			//剥下一层
			lpsLeft++;
			lpsRight--;
		}
		return String.valueOf(res);
	}

	private void set(char[] res, int resLeft, int resRight, char[] chas,
			int chasLeft, int chasRight, int tempLeft, int tempRight) {
		for (int i = tempLeft; i < chasLeft; i++) {
			res[resLeft++] = chas[i];
			res[resRight--] = chas[i];
		}
		for (int i = tempRight; i > chasRight; i--) {
			res[resLeft++] = chas[i];
			res[resRight--] = chas[i];
		}
		System.out.println(res);
	}
}
